package DataStructureAndAlgorithm.Tedukuri.排序;
/*
 * 创建两个堆，一个大根堆，一个小根堆
 * 大根堆用于存放比中位数小的数据，小根堆用于存放大于中位数的数据
 * 这里我们规定大根堆的堆顶数据即为当前输入数据的中位数
 */
import java.util.*;
public class AcWing_106 {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int P = in.nextInt();
        for (int i = 0; i < P; i++){
            int bh = in.nextInt();
            int n = in.nextInt();
            System.out.println(bh + " " + (n + 1) / 2);
            PriorityQueue<Integer> big = new PriorityQueue<>();
            PriorityQueue<Integer> small = new PriorityQueue<>((o1,o2)->o2 - o1);
            int cnt = 0;
            for (int j = 1; j <= n; j++){
                int x = in.nextInt();
                //当小根堆为空或者输入数据小于小根堆堆顶数据（即中位数）时，将该数据插入小根堆，否则插入大根堆
                if (small.isEmpty() || x <= small.peek()){
                    small.add(x);
                }else big.add(x);
                //当小根堆中的数据数量比大根堆大2，将数据向大根堆转移一位
                if (small.size() > big.size() + 1){
                    big.add(small.poll());
                }
                if (big.size() > small.size()){
                    small.add(big.poll());
                }
                if (j % 2 == 1){
                    System.out.print(small.peek() + " ");
                    if (++cnt % 10 == 0){
                        System.out.println();
                    }
                }
            }
            if (cnt % 10 != 0)System.out.println();
        }
    }
}
